package priority_queue.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 前 K 个高频元素
 */
//自定义一个类，此时类中保存了数组中的元素以及出现的频次
class kind implements Comparable<kind>{
    //数组中出现的元素
    int key;
    //元素出现的频次
    int frequency;

    public kind(int key, int frequency) {
        this.key = key;
        this.frequency = frequency;
    }

    @Override
    public int compareTo(kind o) {
        return this.frequency-o.frequency;
    }
}

public class Num347 {
    public int[] topKFrequent(int[] nums, int k) {
          int[] ret=new int[k];
          //先遍历数组，将出现的元素次数以及频次保存到Map集合中
        Map<Integer,Integer> map=new HashMap<>();
        for (int i:nums){
            if (map.containsKey(i)){
                //此时i元素已经出现过，就将频次++
                int times=map.get(i);
                map.put(i,times+1);
            }else{
                //此时i元素第一次出现，就将该元素保存到map集合中
                map.put(i,1);
            }
        }
        //经过集合的遍历之后，将出现频次最高的前k个元素添加到优先级队列中
        Queue<kind> queue=new PriorityQueue<>();
        for (Map.Entry<Integer,Integer>entry : map.entrySet()){
            if (queue.size()<k){
                queue.offer(new kind(entry.getKey(),entry.getValue()));
            }else{
                //判断堆顶元素和当前元素出现的频次，当大于时就替换到堆顶元素
                kind kind=queue.peek();
                if (entry.getValue()>kind.frequency){
                    queue.poll();
                    queue.offer(new kind(entry.getKey(), entry.getValue()));
                }
            }
        }
        //此时堆中就保存了前k个出现频次最大的键值对，遍历堆，将key取出
        int i=0;
        while (!queue.isEmpty()){
            ret[i]=queue.poll().key;
            i++;
        }
        return ret;
    }
}

